package algorithm.leetcode.I201to400;

import algorithm.leetcode.TreeNode;

/**
 * 错误的做法: 参考Q105 从前序遍历和中序遍历构造二叉树
 * 但是按105的做法如果出现节点值一样,则难以找到中序遍历中根节点的位置
 *
 * 实际上只需要用一次前序遍历就可以了
 * 难点在于给出一个叶子节点,叶子节点的两个null子节点也要放进去标记为N
 * 就像leetcode在测试用例中树的表示方法[1,2,3,null,null,1,1]这样去序列化
 */

public class Q297 {
}


class Codec {

    StringBuilder preorderSB = new StringBuilder();
    int index = 0;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        preorder(root);
        return preorderSB.deleteCharAt(preorderSB.length()-1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return build(data.split("#"));
    }

    private void preorder(TreeNode node) {
        if (node == null) {
            preorderSB.append("N").append("#");
            return;
        }
        preorderSB.append(node.val).append("#");
        preorder(node.left);
        preorder(node.right);
    }

    /**
     * 这也是一个难点,递归构造出树,事实上这也是一个前序遍历
     * @param array
     * @return
     */
    private TreeNode build(String[] array) {
        // base case,极其重要
        if (array[index].equals("N")) {
            index++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(array[index++]));
        root.left = build(array);
        root.right = build(array);
        return root;
    }

}